/**
 * LeetCode 534. 二叉树的直径
 * https://leetcode.cn/problems/diameter-of-binary-tree/
 * 给定一个二叉树，计算它的直径长度。
 * 二叉树的直径长度是指树中任意两个节点路径长度的最大值。
 * 这条路径可能穿过也可能不穿过根节点。
 * 路径长度是以边数表示的。
 * 示例 1：
 * 输入：root = [1,2,3,4,5]
 * 输出：3
 * 解释：最长路径是 1->2->3。
 * 示例 2：
 * 输入：root = [1,2]
 * 输出：1
 * 解释：最长路径是 1->2。
 * 注意：本题中，路径长度是以边数表示的，而不是节点数。
 */

public class Solution534 {

    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
    // 记录最大直径的长度
    int maxDiameter = 0;

    public int diameterOfBinaryTree(TreeNode root) {
        maxDepth(root);
        return maxDiameter;
    }

    int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftMax = maxDepth(root.left);
        int rightMax = maxDepth(root.right);
        // 后序位置，顺便计算最大直径
        int myDiameter = leftMax + rightMax;
        maxDiameter = Math.max(maxDiameter, myDiameter);

        return 1 + Math.max(leftMax, rightMax);
    }
}